package sort.insert_sort;

import java.util.Arrays;

/**
 * 时间复杂度： <br />
 * 最优(数组有序)：O(n) <br />
 * 平均：O(n * n) <br />
 * 每趟排序不能确定元素的最终位置 <br />
 * 最优交换 0 次, 最优比较 n 次 <br />
 * 稳定
 *
 * @author yzh
 * @data 2021/3/24 21:46
 */
public class DirectInsert {
    public static void main(String[] args) {
        int[] nums = new int[]{9, 8, -10, 6, 5};
        directInsert(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void directInsert(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int insertVal = nums[i], j = i - 1;
            for (; j >= 0 && nums[j] > insertVal; j--) nums[j + 1] = nums[j];
            nums[j + 1] = insertVal;
        }
    }

    public static void charu(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            // 待插入的数
            int insertValue = nums[i];
            // 被插入的位置，准备和前一个数比较
            int index = i - 1;
            while (index >= 0 && nums[index] > insertValue) {
                nums[index + 1] = nums[index];
                --index;
            }
            nums[index + 1] = insertValue;
        }
    }

}
